"""
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/

154. 寻找旋转排序数组中的最小值 II
困难
相关标签
相关企业
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须尽可能减少整个过程的操作步骤。

 

示例 1：

输入：nums = [1,3,5]
输出：1
示例 2：

输入：nums = [2,2,2,0,1]
输出：0
 

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
 

进阶：这道题与 寻找旋转排序数组中的最小值 类似，但 nums 可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

"""

from typing import List


class Solution:
    def findMin(self, nums: List[int]) -> int:
        """
        与s153问题比较相似，区别在于元素可能是重复的
        分别从left=0和right=n-1开始比较
        1. 如果nums[left]<nums[right],则说明该数组正常，最小值即为nums[left]
        2. 如果nums[left]>nums[right],则说明全局范围内必定存在旋转，继续根据中位数的方式寻找最小值
        3. 如果nums[left]==nums[right],则一切皆有可能，将值记为j,并计算数组中间的值mid，进行比较
        3.1. 如果j<nums[mid],则从nums[left]与nums[mid]之间寻找最小值
        3.2. 如果j>nums[mid],则从nums[mid]与nums[right]之间寻找最小值
        3.3. 如果j==nums[mid],则继续分别从nums[left]与nums[mid]之间，和nums[mid]和nums[right]之间，各自寻找最小值
        以此类推
        """

        
        # 此方法执行时，必定有nums[start]>=nums[right]
        # 此法可解，但效率较低，部分判断可以提前结束
        def findNextMin(nums:List[int],left:int,right:int)->int:
            if left+1>=right:
                return nums[right]
            
            mid=(left+right)//2
            if nums[left]<nums[mid]:
                return findNextMin(nums,mid,right)
            if nums[mid]<nums[right]:
                return findNextMin(nums,left,mid)
            return min(findNextMin(nums,left,mid),findNextMin(nums,mid,right))

        if nums[0]<nums[-1]:
            return nums[0]
        else:
            return findNextMin(nums,0,len(nums)-1)


if __name__=='__main__':
    s=Solution()
    nums=[1]
    res=s.findMin(nums)
    print(res)